package binarytree

// import "container/ring"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// BST插入操作
// 二叉搜索树的插入规则：找到空节点插入
func insertIntoBST(root *TreeNode, val int) *TreeNode {
	// 确定终止条件
	if root == nil {
		// 插入这个位置
		return &TreeNode{Val: val}
	}

	//单层逻辑  使用前序
	// 比较当前大小，确定左右子树查询
	if root.Val > val {
		// 左子树
		root.Left = insertIntoBST(root.Left, val)
	}
	if root.Val < val {
		root.Right = insertIntoBST(root.Right, val)
	}
	return root
}

// 迭代版本 
// class Solution {
// 	public:
// 		TreeNode* insertIntoBST(TreeNode* root, int val) {
// 			if (root == NULL) {
// 				TreeNode* node = new TreeNode(val);
// 				return node;
// 			}
// 			TreeNode* cur = root;
// 			TreeNode* parent = root; // 这个很重要，需要记录上一个节点，否则无法赋值新节点
// 			while (cur != NULL) {
// 				parent = cur;
// 				if (cur->val > val) cur = cur->left;
// 				else cur = cur->right;
// 			}
// 			TreeNode* node = new TreeNode(val);
// 			if (val < parent->val) parent->left = node;// 此时是用parent节点的进行赋值
// 			else parent->right = node;
// 			return root;
// 		}
// 	};